1743E - FTL - CodeForces Solution

#include "bits/stdc++.h"
using namespace std;
#define ll  long long
#define ld  long double  
#define IOS ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define mem(arr,val) memset(arr,val,sizeof(arr))
const int dirx[] = { 0,0,-1,1,1,-1,1,-1 };
const int diry[] = { 1,-1,0,0,1,1,-1,-1 };
const int N = 5e4 + 5;
const ll inf = 1e18;
const int mod = 1e9 + 7;
bool getbit(ll num, int idx) { return ((num >> idx) & 1); }
void set1(int& num, int idx) { num |= (1 << idx); }
void set0(int& num, int idx) { num &= (~(1 << idx)); }
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(int a, int b) { return a / gcd(a, b) * b; }
ll p1, p2, t1, t2, h, s;
ll dp[N];
ll rec(ll i) {
	if (i <= 0)return 0;
	ll& ret = dp[i];
	if (~ret)return ret;
	ret = inf;
	for (ll g = 0; g <= i; g++) {
		
		ll time1 = g * t1;
		ll second = time1 / t2;

		ll use1 = g * (p1 - s);// use first g times
		ll use2 = second * (p2 - s); // how many times will use second

		ret = min(ret, rec(i - use1 - use2) + time1);
		ll dmg = use1 + use2 + p1 + p2 - s; // intersect in last one 
		ll cost = max(time1 + t1, second * t2 + t2);
		ret = min(ret, rec(i - dmg) + cost);

		time1 = g * t2;
		second = time1 / t1;

		use1 = g * (p2 - s);
		use2 = second * (p1 - s);

		ret = min(ret, rec(i - use1 - use2) + time1);
		dmg = use1 + use2 + p1 + p2 - s;
		cost = max(time1 + t2, second * t1 + t1);
		ret = min(ret, rec(i - dmg) + cost);

	}
	return ret;
}
int main() {
	IOS;
	cin >> p1 >> t1 >> p2 >> t2 >> h >> s;
	mem(dp, -1);
	cout << rec(h) << "\n";
	
}